<head>
  <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>План лекций</title>
  <link href=styles/styles.css rel="stylesheet" type="text/css">
</head>
<h2>День 7. Строки.Base</h2>
<ol>
  <li>Простые алгоритмы.</li>
  <ol>
    <li>Z-функция</li>
    <li>Поиск подстроки в строке =)</li>
    <li>Нахождение периода строки</li>
    <li>Нахождение min циклического сдвига строки</li>
    <li>Сортировка строк стандартной функцией sort работает за O(SumLen * log)</li>
  </ol></li>
  <li>Хэши</li>
  <ol>
    <li>Полиномиальный хеш. 2<sup>32</sup> vs 2<sup>64</sup>. Вычисление для подстроки за O(1).</li>
    <li>Антихэш тест: какие их какие не падают, какие падают, с какой вероятностью падают.</li>
    <li>Подстрока в строке</li>
    <li>Подсчет кол-ва палиндромов в строке за O(NlogN)</li>
    <li>Сравнение строк на больше-меньше за O(logN)</li>
    <li>Суффиксный массив, построение за O(Nlog<sup>2</sup>N)</li>
    <li>Подсчет LCP соседних хэшами за O(NlogN) (LCP любых двух считается хэшами за O(logN))</li>
    <li>Решение задачи "общая подстрока" суффиксным массивом (удвоение строки)</li>
    <li>Решение задачи "поиск строки в тексте" за O(|s|*log|T|)</li>
  </ol></li>
  <li>Hash Table</li>
  <ol>
    <li>Реализация открытой адресация (один массив в 1.5 раз больше)</li>
    <li>Реализация на списках (не используется лишняя память)</li>
    <li>Удвоение при переполнении (в лоб передобавляем все элементы)</li>
    <li>Задачи на HashTable и Хэши</li>
    <ol>
      <li>Наибольшая общая подстрока за O(NlogN) (бинпоиск по ответу)</li>
      <li>Наибольший общий подпалиндром за O(NlogN) (бинпоиск по ответу)</li>
    </ol></li>
  </ol></li>
  <li>Бор</li>
  <ol>
    <li>Бор. Построение за суммарную длину строк.</li>
    <li>Алгоритм поиска словарного слова в тексте за O(|text|*max|word|)</li>
    <li>Хранение бора: массив, список, set, hash-таблица, полу-массив.</li>
    <li>Суффиксное дерево. Построение за квадрат.</li>
    <li>Использование суффиксного дерева: поиск строки в тексте за O(|s|) (строим суф.дерево от текста)</li>
    <li>Сжатый бор. Суффиксное дерево теперь использует O(n) памяти, строится за O(n<sup>2</sup>).</li>
    <li>Построение суф.дерева по суф.массиву с LCP за O(n).</li>
  </ol></li>
  <li>Bonus</li>
  <ol>
    <li>Алгоритм Касаи для построения LCP за O(n)</li>
    <li>Автоматы. Детерминированый, недетерминированный. Суффиксный автомат. Только определения.</li>
    <li>Префикс-фунция.</li>
  </ol></li>
</ol>
